const swap = (array: Array<number>, p1:number, p2:number) => {
    [array[p1], array[p2]] = [array[p2], array[p1]]
}
// 冒泡排序
const bubbleSort = (array:Array<number>):Array<number> => {
    const len = array.length
    if (len == 1) return array
    for (let i = len; i--;) {
        for (let j = len; j--;) {
            if (array[j] > array[j + 1]) {
                swap(array, j , j + 1)
            }
        }
    }
    return array
}

// 选择排序
const selectionSort = (array:Array<number>):Array<number> => {
    const len = array.length
    if (len == 1) return array
    for (let i = 0; i < len - 1; i++) {
        let indexMin = i
        for (let j = i; j < len; j++) {
            if (array[indexMin] > array[j]) {
                indexMin = j
            }
        }
        if (i !== indexMin) {
            swap(array, i, indexMin)
        }
    }
    return array
}
// 插入排序
const insertSort = (array:Array<number>):Array<number> => {
    const len = array.length
    if (len == 1) return array
    for (let i = 1; i<len; i--) {
        let j = i
        const value = array[i]
        while (j > 0 && array[j - 1] > value) {
            array[j] = array[j - 1]
            j--
        }
        array[j] = value
    }
    return array
}
// 归并排序
function merge(leftArr: Array<number>, rightArr: Array<number>) {
    const result = []
    while (leftArr.length > 0 && rightArr.length > 0) {
        if (leftArr[0] > rightArr[0]) {
            result.push(leftArr.shift())
        } else {
            result.push(rightArr.shift())
        }
    }
    return result.concat(leftArr).concat(rightArr)   
}

function mergeSort(array: Array<number>): Array<number> {
    if (array.length == 1) return array
    const middle = Math.floor(array.length / 2)
    const left = array.slice(0, middle)
    const right = array.slice(middle)
    return merge(mergeSort(left), mergeSort(right))
}
// 快速排序
const quickSort = (array: Array<number>): Array<number> => {
    const len = array.length
    if (len == 1) return array
    let pivotIndex = Math.floor(len / 2)
    let pivot = array.splice(pivotIndex, 1)[0]
    const left:number[] = []
    const right:number[] = []
    for (let i = 0; i < len; i++) {
        if (array[i] < pivot) {
            left.push(array[i])
        } else {
        right.push(array[i])
        }
    }
    return quickSort(left).concat([pivot], quickSort(right))
}